# 找零钱问题，n,d,缩小问题规模方法
def cc(amount, kinds_of_coin):
    if len(kinds_of_coin) == 0:
        return 0
    if amount == 0:
        return 1
    if amount == 100:
        return 292  # 已有的结果,可以显著的减少递归深度
    # left = amount % kinds_of_coin[0]
    left = amount - kinds_of_coin[0]
    # 分为包含R和不包含R的情况
    if left >= 0:
        return cc(left, kinds_of_coin) + cc(amount, kinds_of_coin[1:])
    else:
        return cc(amount, kinds_of_coin[1:])


def cc2(amount_p, kinds_of_coin_p):
    if amount_p == 0:  # 到达树的叶子节点
        return 1
    if amount_p < 0 or len(kinds_of_coin_p) == 0:
        return 0
    x = []
    for i in range(len(kinds_of_coin_p)):
        coin = kinds_of_coin_p[i]
        new_kinds_coin = kinds_of_coin_p[i:]  # -1是翻转,空才代表末尾。
        # 其实是在构造一棵树
        x.append(cc2(amount_p - coin, new_kinds_coin))

    return sum(x)


def test():
    kinds_of_coin = [50, 25, 10, 5, 1]
    amount = 1000  # 1000竟然达到了最深的递归深度，递归就是很耗内存，是否可以改成迭代？
    print(cc(amount, kinds_of_coin))
    # print(cc2(amount, kinds_of_coin))


def queen(a, n):
    # 这个规模参数就是n
    # 肯定有一个判断位置是否合适的一个函数

    if len(a) == n:
        print(a)
        return  # 这个很重要，只有找到一个才返回
    else:
        for i in range(n):
            if check(a, i, n):
                a.append(i)  # 可以看到a加入之后，还有一个回退的过程
                queen(a, n)
                a.pop()


def check(ls, x, n):
    # 检查在ls的棋局下，能不能在放入x，把这个过程抽象出来之后写8皇后问题就很容易了
    a = []
    length = len(ls)
    for i in range(len(ls)):
        value = ls[i]
        a.append(value)
        a.append(length - i + value)  # 右上角，
        a.append(value + length + i)  # 右下角

    if x in a:
        return False
    else:
        return True

a= []
queen(a, 8)
